﻿#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

//⻓度最⼩的⼦数组

//自己写的
int minSubArrayLen(int target, vector<int>& nums) {
    int left, right;
    left = right = 0;
    int n = nums.size();
    int sum = 0;
    int len = n;

    while (left < n)
    {
        while (right < n)
        {
            sum += nums[right];
            if (sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= (nums[left] + nums[right]);
                left++;
            }
            else
            {
                right++;
            }
        }
        break;
    }
    if (len == n && left == 0)
    {
        return 0;
    }
    else
    {
        return len;
    }
}

//老师写的

int minSubArrayLen2(int target, vector<int>& nums) {
    int sum = 0, len = INT_MAX;
    int n = nums.size();

    for (int left = 0, right = 0; right < n;)
    {
        sum += nums[right];
        while (sum >= target)
        {
            len = min(len, right - left + 1);
            sum -= nums[left];
            left++;
        }
        right++;
    }
    return len == INT_MAX ? 0 : len;
}


//⽆重复字符的最⻓⼦串
int lengthOfLongestSubstring(string s) {
    int len = 0;
    int arr[128] = { 0 };
    int n = s.size() - 1;

    for (int right = 0, left = 0; right <= n;)
    {
        arr[s[right]]++;
        while (arr[s[right]] > 1)
        {
            arr[s[left]]--;
            left++;
        }
        len = max(len, right - left + 1);
        right++;
    }
    return len;
}


//最大连续1的个数
int longestOnes(vector<int>& nums, int k) {
    int n = nums.size();
    int zero = 0;
    int len = 0;

    for (int left = 0, right = 0; right < n;)
    {
        if (nums[right] == 0)
        {
            zero++;
        }
        while (zero > k)
        {
            if (nums[left] == 0)
            {
                zero--;
            }
            left++;
        }
        len = max(len, right - left + 1);
        right++;
    }
    return len;
}


//将x减到0的最小操作数
int minOperations(vector<int>& nums, int x) {
    int sum1 = 0;
    int n = nums.size();
    for (auto a : nums)
    {
        sum1 += a;
    }
    int len = -1;
    int sum2 = 0;
    int target = sum1 - x;
    if (target < 0)
    {
        return -1;
    }

    for (int left = 0, right = 0; right < n; right++)
    {
        sum2 += nums[right];
        while (sum2 > target)
        {
            sum2 -= nums[left];
            left++;
        }
        if (sum2 == target)
        {
            len = max(len, right - left + 1);
        }
    }
    if (len == -1)
    {
        return len;
    }
    else
    {
        return n - len;
    }
}



//水果成篮

class Solution4_1 {
public:
    int totalFruit(vector<int>& fruits) {
        int left = 0, right = 0;
        int Max = 0;
        unordered_map<int, int> hash;
        while (right < fruits.size()) {
            hash[fruits[right]]++;
            while (hash.size() > 2) {
                hash[fruits[left]]--;
                if (hash[fruits[left]] == 0) {
                    hash.erase(fruits[left]);
                }
                left++;
            }
            Max = max(Max, right - left);
            right++;
        }
        return Max + 1;
    }
};


//找到字符串中所有字母异位词
//超时
class Solution5_1 {
public:
    vector<int> findAnagrams(string s, string p) {
        int w = p.size();//窗口大小
        int left = 0;
        int right = left + w;
        sort(p.begin(), p.end());
        vector<int> v; // 记录最终答案
        auto pos = s.begin();

        while (right <= s.size()) {
            string tmp(pos + left, pos + right);
            sort(tmp.begin(), tmp.end());
            if (tmp.compare(p) == 0) {
                v.push_back(left);
            }
            left++;
            right++;
        }
        return v;
    }
};

//判断较为复杂，但是能通过
class Solution5_2 {
public:
    bool IsTheSame(int tmp[], string& p) {
        int arr[26] = { 0 };
        memcpy(arr, tmp,sizeof(int)*26);
        for (auto s : p) {
            arr[s - 'a']--;
            if (arr[s - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        vector<int> v;
        int hash[26] = { 0 };

        while (right < s.size()) {
            hash[s[right] - 'a']++;
            if (right - left + 1 > p.size()) {
                hash[s[left] - 'a']--;
                left++;
            }
            if (right - left + 1 == p.size()) {
                if (IsTheSame(hash, p)) {
                    v.push_back(left);
                }
            }
            right++;
        }
        return v;
    }
};


//优化判断 定义一个count来优化判断，用hash2统计p中所有字符出现的个数，hash记录当前窗口的字符，并且通过count统计有效字符的个数，最后通过这个count来判断
class Solution5_3 {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0, w = p.size();
        vector<int> v;
        int hash1[26] = { 0 }, hash2[26] = { 0 };
        for (auto s : p) {
            hash2[s - 'a']++;
        }
        int count = 0;
        while (right < s.size()) {
            
            hash1[s[right] - 'a']++;
            if (hash1[s[right] - 'a'] <= hash2[s[right] - 'a']) {
                count++;
            }
            if (right - left + 1 > w) {
                hash1[s[left] - 'a']--;
                if (hash1[s[left] - 'a'] < hash2[s[left] - 'a']) {
                    count--;
                }
                left++;
            }
            if (right - left + 1 == w) {
                if (count == w) {
                    v.push_back(left);
                }
            }
            right++;
        }
        return v;
    }
};


//串联所有单词的子串
class Solution6_1 {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2;
        for (auto s : words) {
            hash2[s]++;
        }
        vector<int> v;
        int len = words[0].size();
        if (len > s.size()) {
            return {};
        }
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash1;
            int left = i, right = i;
            int count = 0;
            while (right < s.size()) {
                if (right + len > s.size()) {
                    break;
                }
                string cur(s.begin() + right, s.begin() + right + len);//当前字符串
                hash1[cur]++;   //当前字符串
                //判断当前字符串是否为有效字符串
                if (hash1[cur] <= hash2[cur]) {
                    count++;
                }
                //判断当前字符串中是否大于子串长度
                if (right - left >= len * words.size()) {
                    string tmp(s.begin() + left, s.begin() + left + len);//字符出窗口前，更新hash1
                    hash1[tmp]--;
                    if (hash1[tmp] < hash2[tmp]) {
                        count--;
                    }
                    left += len;
                }
                if (count == words.size()) {
                    v.push_back(left);
                }
                right += len;
            }
        }
        return v;//
    }
};

class Solution6_2 {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2;
        for (auto s : words) {
            hash2[s]++;
        }
        vector<int> v;
        int len = words[0].size();
        if (len > s.size()) {
            return {};
        }
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash1;
            int left = i, right = i;
            int count = 0;
            while (right < s.size()) {
                if (right + len > s.size()) {
                    break;
                }
                string cur = s.substr(right, len);//当前字符串
                hash1[cur]++;   //当前字符串
                //判断当前字符串是否为有效字符串
                if (hash1[cur] <= hash2[cur]) {
                    count++;
                }
                //判断当前字符串中是否大于子串长度
                if (right - left >= len * words.size()) {
                    string tmp = s.substr(left, len);//字符出窗口前，更新hash1
                    hash1[tmp]--;
                    if (hash1[tmp] < hash2[tmp]) {
                        count--;
                    }
                    left += len;
                }
                if (count == words.size()) {
                    v.push_back(left);
                }
                right += len;
            }
        }
        return v;
    }
};


//count++ -- 部分，通过查找来减少创建次数，从而达到优化算法的目的
class Solution6_3 {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2;
        for (auto s : words) {
            hash2[s]++;
        }
        vector<int> v;
        int len = words[0].size();
        if (len > s.size()) {
            return {};
        }
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash1;
            int left = i, right = i;
            int count = 0;
            while (right < s.size()) {
                if (right + len > s.size()) {
                    break;
                }
                string cur = s.substr(right, len);//当前字符串
                hash1[cur]++;   //当前字符串
                //判断当前字符串是否为有效字符串,根据hash算法的特性，如果哈希表中不存在这个值，他会多创建一个，那么我们需要在创建之前去查询是否存在这个值，查找比创建快，能够大大优化算法，同下
                if (hash2.count(cur) && hash1[cur] <= hash2[cur]) {
                    count++;
                }
                //判断当前字符串中是否大于子串长度
                if (right - left >= len * words.size()) {
                    string tmp = s.substr(left, len);//字符出窗口前，更新hash1
                    hash1[tmp]--;
                    if (hash2.count(tmp) && hash1[tmp] < hash2[tmp]) {
                        count--;
                    }
                    left += len;
                }
                if (count == words.size()) {
                    v.push_back(left);
                }
                right += len;
            }
        }
        return v;
    }
};


//最小覆盖子串
class Solution7_1 {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        if (n < t.size()) {
            return "";
        }
        int hash1[60] = { 0 }, hash2[60] = { 0 };
        //符合的子串
        for (auto w : t) {
            hash2[w - 'A']++;
        }
        int left = 0, right = 0, count = 0, Min = INT_MAX;
        unordered_map<int, int> ret;//记录最终答案的起始位置和长度
        while (right < n) {
            hash1[s[right] - 'A']++;
            //当前字符在子串中，且大小小于等于对应个数，则count++，count用于判断，count是hash1中有效子串的个数，当有效子串个数等于t.size()时,说明此时hash1可能是答案之一
            if (hash1[s[right] - 'A'] <= hash2[s[right] - 'A']) {
                count++;
            }
            //如果count == 子串大小，则循环出，直到当前窗口不满足条件，此时需要right++，在窗口中加入新的成员。
            while (count == t.size()) {
                if (right - left + 1 < Min) {
                    ret.insert({ right - left + 1,left });
                    Min = right - left + 1;
                }
                hash1[s[left] - 'A']--;
                if (hash1[s[left] - 'A'] < hash2[s[left] - 'A']) {
                    count--;
                }
                left++;
            }
            right++;
        }
        if (ret.empty()) {
            return "";
        }
        else {
            return s.substr(ret[Min], Min);
        }
    }
};


class Solution7_2 {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        if (n < t.size()) {
            return "";
        }
        int hash1[60] = { 0 }, hash2[60] = { 0 };
        //符合的子串
        for (auto w : t) {
            hash2[w - 'A']++;
        }
        int left = 0, right = 0, count = 0, Min = INT_MAX, begin = -1;;//用Min 和 begin来记录起始位置和大小
        while (right < n) {
            hash1[s[right] - 'A']++;
            //当前字符在子串中，且大小小于等于对应个数，则count++，count用于判断，count是hash1中有效子串的个数，当有效子串个数等于t.size()时,说明此时hash1可能是答案之一
            if (hash1[s[right] - 'A'] <= hash2[s[right] - 'A']) {
                count++;
            }
            //如果count == 子串大小，则循环出，直到当前窗口不满足条件，此时需要right++，在窗口中加入新的成员。
            while (count == t.size()) {
                if (right - left + 1 < Min) {
                    Min = right - left + 1;
                    begin = left;
                }
                hash1[s[left] - 'A']--;
                if (hash1[s[left] - 'A'] < hash2[s[left] - 'A']) {
                    count--;
                }
                left++;
            }
            right++;
        }
        if (begin == -1) {
            return "";
        }
        else {
            return s.substr(begin, Min);
        }
    }
};


using namespace std;
int main()
{
    //⻓度最⼩的⼦数组
    //vector<int> s({ 1,2,3,4,5 });
    //minSubArrayLen(15, s);


    //⽆重复字符的最⻓⼦串
   //string s("abcabcbb");
   //cout << lengthOfLongestSubstring(s);

    //最大连续1的个数
   /* vector<int> nums({ 1,1,1,0,0,0,1,1,1,1,0 });
    longestOnes(nums, 2);*/

    //vector<int> nums({ 1,1 });
    //cout << minOperations(nums, 3);

    Solution6_2 s;
    string str("barfoofoobarthefoobarman");
    vector<string> p({ "bar","foo","the" });
    vector<int> tmp = s.findSubstring(str,p);

    return 0;
}